package zcw.com.lib_leet_code;

/**
 * Created by 朱城委 on 2021/8/18.<br><br>
 *
 * 困难：寻找旋转排序数组中的最小值 II
 */
public class Topic154 {

    public static void main(String[] args) {
        Topic154 instance = new Topic154();

        int[] array = new int[] {3,4,5,1,2};
        System.out.println(instance.findMin(array));

        array = new int[] {4,5,6,7,0,1,2};
        System.out.println(instance.findMin(array));

        array = new int[] {11,13,15,17};
        System.out.println(instance.findMin(array));

        array = new int[] {2,1};
        System.out.println(instance.findMin(array));

        array = new int[] {1,3,5};
        System.out.println(instance.findMin(array));

        array = new int[] {2,2,2,0,1};
        System.out.println(instance.findMin(array));

        array = new int[] {10,1,10,10,10};
        System.out.println(instance.findMin(array));
    }

    public int findMin(int[] nums) {
        int left = 0;
        int right = nums.length - 1;

        while (left < right) {
            int mild = (left + right) / 2;

            if(nums[mild] > nums[right]) {
                left = mild + 1;
            }
            else if(nums[mild] < nums[right]) {
                right = mild;
            }
            else {
                right--;
            }
        }

        return nums[left];
    }
}
